import java.util.HashMap;

public class CanCross {

    public boolean canCross1(int[] stones) {
        int n = stones.length;
        boolean[][] dp = new boolean[n][n];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(stones[i], i);
        }
        dp[0][0] = true;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= i; j++) {
                if (!map.containsKey(stones[i] - j)) continue;
                dp[i][j] = isValid(dp, j, map.get(stones[i] - j));
                if (i == n - 1 && dp[i][j]) return true;
            }
        }
        return false;
    }

    public boolean isValid(boolean[][] dp, int target, int index) {
        boolean a = target + 1 < dp[0].length ? dp[index][target + 1] : false;
        boolean b = dp[index][target];
        boolean c = dp[index][target - 1];
        return a || b || c;
    }

    public boolean canCross(int[] stones) {
        int n = stones.length;
        boolean[][] dp = new boolean[n][n + 1];
        dp[0][0] = true;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int temp = stones[i] - stones[j];
                if (temp <= j + 1) {
                    dp[i][temp] = dp[j][temp] || dp[j][temp + 1] || dp[j][temp - 1];
                    if (i == n - 1 && dp[i][j]) return true;
                }
            }
        }
        return false;
    }
}
